package MyDFS;

import java.util.ArrayList;
import java.util.List;

public class Leetcode08_07 {
    public static String[] permutation(String S) {
        ArrayList<String> res = new ArrayList<String>();
        int len = S.length();
        if(len <= 0){
            return res.toArray(new String[res.size()]);
        }
        boolean[] used = new boolean[len];
        String path = new String();

        dfs(S, len, 0,used,path,res);
        return res.toArray(new String[res.size()]);
    }

    public static void dfs(String S, int len, int depth, boolean[] used, String path, ArrayList<String> res){
        if(depth == len){
            res.add(path);
            System.out.println(path);
            return;
        }

        for(int i=0; i<len; i++){
            if(!used[i]){
                String newPath = new String(path);
                newPath += S.charAt(i);

                boolean[] newUsed = new boolean[len];
                System.arraycopy(used,0, newUsed, 0, len);
                newUsed[i] = true;

                dfs(S, len, depth+1, newUsed, newPath, res);
            }
        }
    }

    public static void main(String[] args) {
        String ss = "adb";
        permutation(ss);
    }
}
